import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int testCases = Integer.parseInt(br.readLine());
		while(testCases-- != 0) {
			int n = Integer.parseInt(br.readLine().trim());
			String str = br.readLine();
			StringTokenizer sToken = new StringTokenizer(str, " ");
			
			Data[] d = new Data[n];
			for(int i = 0; i < n; i++) {
				d[i] = new Data(Integer.parseInt(sToken.nextToken()), i + 1);
			}
			Arrays.sort(d);
			
			int[][] lookup = new int[n][n];
			for(int i = 0; i < n; i++) {
				lookup[i][i] = d[i].index;
			}
			
			for(int i = 0; i < n; i++) {
				for(int j = i - 1; j >= 0; j--) {
					lookup[i][j] = (d[i].index > d[j].index) ? lookup[i][j + 1] - 1 : lookup[i][j + 1];  
				}
				
				for(int j = i + 1; j < n; j++) {
					lookup[i][j] = (d[i].index > d[j].index) ? lookup[i][j - 1] - 1 : lookup[i][j - 1];
				}
			}
			
			
			int mem[][] = new int[n][n];
			for(int i = 0; i < n; i++) {
				mem[i][i] = n;
			}
			
			for(int k = 1; k < n; k++) {
				for(int i = 0; i < n && i + k < n; i++) {
					int start = i, end = i + k;
					int step = n - end + start;
					mem[start][end] = Math.max((step * lookup[end][start]) + mem[start][end - 1], (step * lookup[start][end]) + mem[start + 1][end]);
				}
			}
			System.out.println(mem[0][n - 1]);
		}
	}
	
	
	private static class Data implements Comparable<Data> {
		
		int num, index;
		
		private Data(int n, int i) {
			num = n;
			index = i;
		}

		@Override
		public int compareTo(Data o) {
			return num - o.num;
		}
	}

}
